package com.ztom.top100;

/**
 * 比特位计数
 * <p>
 * https://leetcode-cn.com/problems/counting-bits/
 *
 * @author ZhangTao
 */
public class Code82CountBits {

    public int[] countBits(int n) {
        if (n < 0) {
            return null;
        }
        if (n == 0) {
            return new int[]{0};
        }
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            res[i] = count(i);
        }
        return res;
    }

    private int count(int i) {
        int count = 0;
        while (i > 0) {
            count++;
            // 抹除最右侧的 1
            i &= i - 1;
        }
        return count;
    }
}
